We represent planning as a set of loosely coupled network flow problems,where each network corresponds to one of the state variables in the planningdomain. The network nodes correspond to the state variable values and thenetwork arcs correspond to the value transitions. The planning problem is tofind a path (a sequence of actions) in each network such that, when merged,they constitute a feasible plan. In this paper we present a number of integerprogramming formulations that model these loosely coupled networks with varyingdegrees of flexibility. Since merging may introduce exponentially many orderingconstraints we implement a so-called branch-and-cut algorithm, in which theseconstraints are dynamically generated and added to the formulation when needed.Our results are very promising, they improve upon previous planning as integerprogramming approaches and lay the foundation for integer programmingapproaches for cost optimal planning.
展开▼
